// hdu3436
// 题意：给定n(<=10^8)的数[1, n]，初始按序排列。现在进行q(<=10^5)次操作，
//       操作有一下三种：
//        1.Top x:将x移到队首;
//        2.Query x: 询问当前编号为x人的位置;
//        3.Rank x: 询问当前在位置x的人的编号;
//
// 题解：难点在于n很大，发现除了top操作外，其他的区间都是连续一段一段的，
//       所以可以离散化，将top点和每一段两个top间连续的区间离散化为点，
//       个数最多是O(q)个，然后就可以改一下splay来维护这三个操作。
//       现在每个节点除了有代表的元素外还有区间长度，splay节点需要增加
//       维护的size信息。
//
//       另外一定要记得给序列前后增加哨兵节点，防止越界出错。
//
// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>

//#define __DEBUG

int const maxn = 300007;
int const inf = 1 << 30;

struct command { int type; int num; };

command cmd[maxn];
std::string opt;
int n, m;
std::vector<std::pair<int, int> > disc; // pair<num, len>

namespace splay_tree
{
	struct node
	{
		node() { rsize = size = len = 0; num = inf; }
		void set_child(node * c, int is_right) { child[is_right] = c; c->parent = this; }
		bool is_right() { return this == parent->child[1]; }

		int rsize, size, num, len;
		node * child[2], * parent;
	} * root, memory[maxn], * nil;

//	void relax(node * t) { // relax tag on t }

	void update(node * t)
	{
		t->size = t->child[0]->size + t->child[1]->size + 1;
		t->rsize = t->child[0]->rsize + t->child[1]->rsize + t->len;
	}

	void rot(node * t)
	{
		node * p = t->parent;
		//relax(p); relax(t);
		bool is_right = t->is_right();
		p->parent->set_child(t, p->is_right());
		p->set_child(t->child[!is_right], is_right);
		t->set_child(p, !is_right);
		update(p);
		if (p == root) root = t;
	}

	void splay(node * t, node * parent)
	{
		while (t->parent != parent) {
			if (t->parent->parent == parent)
				rot(t);
			else
				(t->is_right() == t->parent->is_right()) ?
					(rot(t->parent), rot(t)) :
						(rot(t), rot(t));
		}
		update(t);
	}

	void splay(node * t) { splay(t, nil); }

	node * node_alloc(int p)
	{
		memory[p].child[0] = memory[p].child[1] = nil;
		memory[p].size = 1;
		memory[p].rsize = memory[p].len = disc[p].second;
		memory[p].num = disc[p].first;
		return memory + p;
	}

	node * build(int l, int r)
	{
		if (l >= r) return nil;
		int mid = (l + r) / 2;
		node * t = node_alloc(mid);
		t->set_child(build(l, mid), 0);
		t->set_child(build(mid + 1, r), 1);
		update(t);
		return t;
	}

	void init(int n)
	{
		nil = new node;
		root = build(0, n);
		root->parent = nil;
	}

	node * select(int k)
	{
		for (node * t = root; ; ) {
			//relax(t);
			int c = t->child[0]->size;
			if (k == c) return t;
			if (k > c)
				k -= c + 1, t = t->child[1];
			else
				t = t->child[0];
		}
	}

	void in_order(node * tmp)
	{
		if (tmp == nil) return;
		in_order(tmp->child[0]);
		std::cerr << '(' << tmp->num << ", " << tmp->len << ") ";
		in_order(tmp->child[1]);
	}

	void print()
	{
#ifdef __DEBUG
		std::cerr << "the current splay tree seq is: ";
		in_order(root);
		std::cerr << '\n';
#endif
	}

	void insert_front(node * x)
	{
		node * t = select(0);
		node * tr = select(1);
		splay(t);
		splay(tr, t);
		x->set_child(tr->child[0], 0);
		tr->set_child(x, 0);
		update(tr);
	}

	void top(int pos)
	{
		node * now = memory + pos;
		splay(now);
		int p = now->child[0]->size;
		node * t = select(p - 1);
		node * tr = select(p + 1);
		splay(t);
		splay(tr, t);
		tr->child[0] = nil;
		update(tr);
		splay(tr);
		insert_front(now);
	}

	int query(int p)
	{
		node * tmp = memory + p;
		splay(tmp);
		return tmp->child[0]->rsize + 1;
	}

	int rank(int k)
	{
		for (node * t = root; ; ) {
			int c = t->child[0]->rsize;
			if (k > c && k <= c + t->len) return t->num + k - c - 1;
			if (k > c + t->len)
				k -= c + t->len, t = t->child[1];
			else
				t = t->child[0];
		}
	}
};

std::pair<int, int> get_index_num(int x) // pair<num, pos>, get leq than x's largest num
{
	int p = std::upper_bound(disc.begin(), disc.end(), std::make_pair(x, inf)) - disc.begin() - 1;
	return std::make_pair(disc[p].first, p);
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	for (int ti = 1; ti <= T; ti++) {
		std::cout << "Case " << ti << ":\n";
		std::cin >> n >> m;
		std::vector<int> tmp;
		disc.clear();
		for (int i = 0; i < m; i++) {
			std::cin >> opt >> cmd[i].num;
			if (opt[0] == 'T') cmd[i].type = 0;
			else if (opt[0] == 'Q') cmd[i].type = 1;
			else cmd[i].type = 2;
			if (!cmd[i].type) tmp.push_back(cmd[i].num);
		}
		std::sort(tmp.begin(), tmp.end());
		disc.push_back(std::make_pair(0, 0));
		int last = 0;
		for (std::vector<int>::iterator it = tmp.begin(); it != tmp.end(); ++it) {
			int now = *it;
			if (now == last) continue;
			if (now - last == 1) {
				disc.push_back(std::make_pair(now, 1));
			} else {
				disc.push_back(std::make_pair(last + 1, now - last - 1));
				disc.push_back(std::make_pair(now, 1));
			}
			last = now;
		}
		if (last != n)
			disc.push_back(std::make_pair(last + 1, n - last));
		disc.push_back(std::make_pair(inf, inf));

		splay_tree::init(disc.size());
		splay_tree::print();
		for (int i = 0; i < m; i++) {
			std::pair<int, int> t = get_index_num(cmd[i].num);
			if (!cmd[i].type) {
				splay_tree::top(t.second);
				splay_tree::print();
			} else if (cmd[i].type == 1) {
				int tpos = splay_tree::query(t.second);
				std::cout << cmd[i].num - t.first + tpos << '\n';
			} else {
				std::cout << splay_tree::rank(cmd[i].num) << '\n';
			}
		}
	}
}

